package q456_find132pattern;

import java.util.Deque;
import java.util.LinkedList;

public class Solution_2 {

    /*
    通过枚举所谓 '1' 位置得元素来寻找是否存在满足条件的子集
     */
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        Deque<Integer> candidateK = new LinkedList<Integer>();
        // 压入最后一个元素
        candidateK.push(nums[n - 1]);
        int maxK = Integer.MIN_VALUE;

        /*
        遍历到一个新元素时 考虑其是否可以作为 3。如果它作为 3，那么数据结构中所有严格小于它的元素都可以作为 2，
        我们将这些元素全部从数据结构中移除，并且使用一个变量维护所有被移除的元素的最大值。
        这些被移除的元素都是可以真正作为 2 的，并且元素的值越大，那么我们之后找到 1 的机会也就越大。

        对于栈的结构应该是栈底元素大 而栈顶元素小的结构 例如 我们遇到 1 2 3 4 5 就会被全部压入栈
         */
        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] < maxK) {
                return true;
            }

            while (!candidateK.isEmpty() && nums[i] > candidateK.peek()) {
                maxK = candidateK.pop();
            }
            if (nums[i] > maxK) {
                candidateK.push(nums[i]);
            }
        }

        return false;

    }
}
